package 二叉树练习题;

public class F如何把二叉树转换为双向链表 {
    /**
     * 输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
     * 要求不能创建任何新的结点，只能调整结点的指向
     */
    private static BiTNode pHead = null;
    private static BiTNode pEnd = null;

    public static void inOrderBSTree(BiTNode root) {
        if (null == root) {
            return;
        }
        inOrderBSTree(root.lchild);

        root.lchild = pEnd;
        if (null == pEnd) {
            pHead = root;
        } else {
            pEnd.rchild = root;
        }
        pEnd = root;
        inOrderBSTree(root.rchild);
    }

    public static void main(String[] args) {
        int arr[] = {1, 2, 3, 4, 5, 6, 7};
        BiTNode root;
        root = B如何把一个有序的整数数组放到二叉树中.arraytotree(arr, 0, arr.length - 1);
        inOrderBSTree(root);
        BiTNode cur;
        System.out.println("转换成双向链表正向遍历：");
        for (cur = pHead; cur != null; cur = cur.rchild) {
            System.out.print(cur.data + "  ");
        }
        System.out.println();
        System.out.print(" 转换后双向链表逆序遍历");
        for (cur = pEnd; cur != null; cur = cur.lchild) {
            System.out.print(cur.data + " ");
        }
    }
}
